package com.leetcode.algorithm.y22.m07.w4;

/**
 * 707. 设计链表
 * 
 * https://leetcode.cn/problems/design-linked-list/
 * 
 * @author jie.deng
 *
 */
class MyLinkedList {

	private Node head;
	private Node tail;
	private int cnt;

	public MyLinkedList() {
	}

	public int get(int index) {
		Node node = getNodeAtIndex(index);
		return node == null ? -1 : node.val;
	}

	private Node getNodeAtIndex(int index) {
		if (index < 0 || index >= this.cnt) {
			return null;
		}
		Node cur = this.head;
		while (index > 0) {
			cur = cur.next;
			index--;
		}
		return cur;
	}

	public void addAtHead(int val) {
		Node node = new Node(val, null, null);
		if (cnt == 0) {
			this.head = node;
			this.tail = node;
			node.prev = node;
			node.next = node;
		} else {
			node.next = this.head;
			this.head.prev = node;
			node.prev = this.tail;
			this.tail.next = node;
			this.head = node;
		}
		cnt++;
	}

	public void addAtTail(int val) {
		Node node = new Node(val, null, null);
		if (cnt == 0) {
			this.head = node;
			this.tail = node;
			node.prev = node;
			node.next = node;
		} else {
			node.next = this.head;
			node.prev = this.tail;
			this.head.prev = node;
			this.tail.next = node;
			this.tail = node;
		}
		cnt++;
	}

	public void addAtIndex(int index, int val) {
		if (index <= 0) {
			addAtHead(val);
		} else if (index == cnt) {
			addAtTail(val);
		} else if (index < cnt) {
			Node cur = getNodeAtIndex(index);
			Node node = new Node(val, cur.prev, cur);
			cur.prev.next = node;
			cur.prev = node;
			cnt++;
		}
	}

	public void deleteAtIndex(int index) {
		Node cur = getNodeAtIndex(index);
		if (cur == null) {
			return;
		}
		cur.prev.next = cur.next;
		cur.next.prev = cur.prev;
		if (cur == head) {
			head = cur.next;
		}
		if (cur == tail) {
			tail = cur.prev;
		}
		cnt--;
	}

	private static class Node {
		int val;
		Node next;
		Node prev;

		Node(int val, Node prev, Node next) {
			this.val = val;
			this.prev = prev;
			this.next = next;
		}
	}
}